#define MAX_STR_LEN 32

typedef struct Trie {
    struct Trie* children[26];
    bool isEnd;
} Trie;


void initTrie(Trie* trie) {
    for (int i = 0; i < 26; i++) {
        trie->children[i] = NULL;
    }
    trie->isEnd = false;
}

bool insertTrie(Trie* trie, const char* word) {
    Trie* node = trie;
    int len = strlen(word);
    for (int i = 0; i < len; i++) {
        char ch = word[i];
        int index = ch - 'a';
        if (node->children[index] == NULL) {
            node->children[index] = (Trie*)malloc(sizeof(Trie));
            initTrie(node->children[index]);
        }
        node = node->children[index];
    }
    node->isEnd = true;
    return true;
}

bool searchTrie(const Trie* trie, const char* word) {
    Trie* node = trie;
    int len = strlen(word);
    for (int i = 0; i < len; i++) {
        char ch = word[i];
        int index = ch - 'a';
        if (node->children[index] == NULL || !node->children[index]->isEnd) {
            return false;
        }
        node = node->children[index];
    }
    return node != NULL && node->isEnd;
}

char* longestWord(char** words, int wordsSize) {
    Trie* trie = (Trie*)malloc(sizeof(Trie));
    initTrie(trie);
    for (int i = 0; i < wordsSize; i++) {
        insertTrie(trie, words[i]);
    }
    char* longest = "";
    for (int i = 0; i < wordsSize; i++) {
        if (searchTrie(trie, words[i])) {
            if (strlen(words[i]) > strlen(longest) || (strlen(words[i]) == strlen(longest) && strcmp(words[i], longest) < 0)) {
                longest = words[i];
            }
        }
    }
    return longest;
}
